package DataStructure.graph;

import java.util.*;

//有向加权图
public class DWGraph {
    private int V;//顶点数量
    private int E;//边数量
    private Deque<Edge> edge;//边
    private int[] in;//入度
    private int[] out;//出度
    private Deque<Edge>[] adj;//邻接表

    
    public DWGraph(int v) {
        V = v;
        E = 0;
        edge=new ArrayDeque<>();
        in=new int[v];
        out=new int[v];
        adj = new ArrayDeque[v];
        for (int i = 0; i < adj.length; i++) {
            adj[i]=new ArrayDeque<>();
        }
    }
    //fix
    public Deque<Edge> near(int v){
        return adj[v];
    }

    public void addEdge(int v,int w,double weight){
        Edge e=new Edge(v,w,weight);
        if(adj[v].contains(e))
            return;
        edge.add(new Edge(v,w));
        out[v]++;
        in[w]++;
        adj[v].add(e);
        E++;
    }


    //最短路径
    //dijkstra算法(基于贪心思想，但已经访问过的顶点不一定是最优解)
    Edge[] diedges;//存储最短路径所有边，表示最短路径上到某个点的边
    double[] dis;//从起点到其他点的最短路径
    Queue<Edge> pq;//存储有向边并排序
    public Edge[] dijkstra(DWGraph G, int v){
        diedges= new Edge[G.V];
        dis=new double[G.V];
        Arrays.fill(dis,Double.MAX_VALUE);
        dis[v]=0;//起点距离为0
        pq=new PriorityQueue<>((o1, o2) -> (int) (o1.weight()-o2.weight()));
        pq.add(new Edge(v,v,0));//从起点开始
        while (!pq.isEmpty()){
            Edge tmp=pq.poll();
            diedges[tmp.to()]=tmp;
            relax(G,tmp.to());//每次选出权重最小的边，这条边下一个点一定已经更新，那么后面的点也需要更新
        }
        return diedges;

    }
    public void relax(DWGraph G, int v){
        if(G.near(v)!=null){
            for (Edge e : G.near(v)) {
                int w=e.to();
                //对于以v为起点的边,如果下一个顶点需要更新(或者未访问)，添加这条边并更新，不用考虑已经访问
                if(dis[v]+e.weight()<dis[w]){
                    pq.add(e);
                    dis[w]=dis[v]+e.weight();
                }
            }
        }
    }

    //floyd算法(可以求所有顶点到其他顶点的最短路径，采用邻接矩阵)
    int[][] path;//存储从i到j的某个中间点
    public int[] floyd(int[][] G,int v){
        int n=G.length;//顶点数量
        path=new int[n][n];
        //分别枚举中间点，起点，终点
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if(G[i][j]>G[i][k]+G[k][j]){
                        G[i][j]=G[i][k]+G[k][j];
                        path[i][j]=k;
                    }
                }
            }
        }
        return G[v];
    }

    //关键路径 todo
    public void keyPath(){

    }
}
